package com.clstu.greedy;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * 贪心算法解决广播覆盖最少的建设的问题
 */
public class GreedyAlgrithm {
    public static void main(String[] args) {
        //建广播站
        HashSet<String> hs1 = new HashSet<>();
        hs1.add("北京");
        hs1.add("上海");
        hs1.add("天津");

        HashSet<String> hs2 = new HashSet<>();
        hs2.add("北京");
        hs2.add("广州");
        hs2.add("深圳");

        HashSet<String> hs3 = new HashSet<>();
        hs3.add("成都");
        hs3.add("上海");
        hs3.add("杭州");

        HashSet<String> hs4 = new HashSet<>();
        hs4.add("北京");
        hs4.add("天津");

        HashSet<String> hs5 = new HashSet<>();
        hs5.add("杭州");
        hs5.add("大连");

        HashMap<String,HashSet<String>> broadCasts = new HashMap<>();
        broadCasts.put("K1",hs1);
        broadCasts.put("K2",hs2);
        broadCasts.put("K3",hs3);
        broadCasts.put("K4",hs4);
        broadCasts.put("K5",hs5);
        //遍历得到广播站
        HashSet<String> areas = new HashSet<>();
        for (Map.Entry<String, HashSet<String>> entry : broadCasts.entrySet()) {
            for (String regStr : entry.getValue()) {
                areas.add(regStr);
            }
        }
//        System.out.println(areas);
        //思路:贪心算法
        //遍历,每次取覆盖最广的建设
        HashSet<String> selected = new HashSet<>();
        while (true) {
            //如果覆盖完
            if(areas.isEmpty()){
                break;
            }
            //找到覆盖最广的广播站
            String maxBro = null;
            for (Map.Entry<String, HashSet<String>> entry : broadCasts.entrySet()) {
                String key = entry.getKey();
                HashSet<String> temp = entry.getValue();
                temp.retainAll(areas);//求交集,即能覆盖的范围
                //判断是否是最优的
                if(temp.size()>0 && (maxBro == null || temp.size()>broadCasts.get(maxBro).size())){
                    maxBro = key;
                }
            }
            //如果找到最优解
            if(maxBro!=null){
                selected.add(maxBro);
                //删除被覆盖的
                areas.removeAll(broadCasts.get(maxBro));
            }
        }
        //输出结果
        System.out.println(selected);

    }
}
